package listbyorder.access301_400.test329;

import java.util.HashMap;

public class Solution1 {

    // 超时， 加Hashmap
    int maxPath = 0;

    // 最长的递增序列
    public int longestIncreasingPath(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return maxPath;
        int r = matrix.length;
        int c = matrix[0].length;

        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                HashMap<String, Integer> memo = new HashMap<>();
                int curLen = dfs(matrix, i, j, r, c, Integer.MIN_VALUE, memo);
                maxPath = Math.max(curLen, maxPath);
            }
        }
        return maxPath;
    }

    private int dfs(int[][] matrix, int i, int j, int r, int c, int pre, HashMap<String, Integer> memo) {
        if (i < 0 || j < 0 || i == r || j == c || matrix[i][j] <= pre) return 0;
        String cur = i + "@" + j;
        if (memo.containsKey(cur)) {
            return memo.get(cur);
        }
        int num = matrix[i][j];
        int res = Math.max(dfs(matrix, i + 1, j, r, c, num, memo), dfs(matrix, i - 1, j, r, c, num, memo));
        res = Math.max(res, dfs(matrix, i, j + 1, r, c, num, memo));
        res = Math.max(res, dfs(matrix, i, j - 1, r, c, num, memo));
        memo.put(cur, res + 1);
        return res + 1;
    }
}
